package com.kehao.leetcode.hard.tree_graph;

import com.kehao.utils.LeetCodeUtil;
import org.junit.Test;

import java.util.*;

//

public class CanFinishSolution {
    int[] visit;
    List<Integer>[] listArray;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visit = new int[numCourses];
        listArray= new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            listArray[i] = new ArrayList<>();
        }
        for(int[] num:prerequisites){
            listArray[num[1]].add(num[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if(visit[i]==0) {
                if(dfs(i)==false) return false;
            }
        }
        return true;
    }

    private boolean dfs(int i){
        if(visit[i]==1) return false;
        if(visit[i]==2) return true;
        visit[i] = 1;
        for(int j : listArray[i]){
            if(dfs(j)==false) return false;
        }
        visit[i] = 2;
        return true;
    }

    @Test
    public void test(){
        String s = LeetCodeUtil.bracketTransform("[[1,0],[0,1]]");
        System.out.println(s);
    }

    @Test
    public void test01(){
        int numCourses = 2;
        int[][] prerequisites = {{1,0}};
        System.out.println(canFinish(numCourses, prerequisites));
    }

    @Test
    public void test02(){
        int numCourses = 2;
        int[][] prerequisites = {{1,0},{0,1}};
        System.out.println(canFinish(numCourses, prerequisites));
    }
}
